note:两个特质:
- 与运算的定义:
- 若$n\&1=0$,则$n$的二进制中最右一位为0
- 若$n\&1=1$,则$n$的二进制中最右一位为1
- $n\&(n-1)$:表示二进制数字$n$最右边的1变为0,其余不变
- 因为$(n-1)$表示二进制数字$n$最右边的1变为0,此1右边的0都变为1
题目描述
请实现一个函数,输入一个整数(以二进制串形式),输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。
示例 1:
1 | 输入:00000000000000000000000000001011 |
示例 2:
1 | 输入:00000000000000000000000010000000 |
示例 3:
1 | 输入:11111111111111111111111111111101 |
提示:
- 输入必须是长度为 32 的 二进制串 。
方法一:按位遍历
思路
按位遍历,利用$n\&1$来判断最右边是否为1,然后进行无符号右移,直到二进制中不存在1为止。
代码
1 | class Solution { |
复杂度分析
- 时间复杂度$O(logn)$。按位遍历的循环过程需要循环$logn$,其中$n$表示最高位1所在的位数
- 空间复杂度$O(1)$。
方法二:巧用$n\&(n-1)$
思路
利用$n\&(n-1)$能将二进制数字的最右边的1变为0的性质,循环消去最右的1,计算要几次消完,就说明有几个1
代码
1 | class Solution { |
复杂度分析
- 时间复杂度$O(M)$。M为二进制中1的个数。
- 空间复杂度$O(1)$。
原文链接: https://zijian.wang/2021/06/07/15 二进制中1的个数/
版权声明: 转载请注明出处.